/**
 *传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
 *
 * 传送带上的第 i个包裹的重量为weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
 *
 * 返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。
 *
 * 链接：https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days
 * 题解：https://labuladong.gitee.io/algo/2/20/31/
 */
class ShipWithinDays {
    public int shipWithinDays(int[] weights, int days) {
        int left=0;
        int right=1;
        for(int weight:weights) {
            left=Math.max(left,weight);
            right+=weight;
        }
        while(left<right) {
            int mid=left+((right-left)>>>1);
            if(f(mid,weights)<days) {
                right=mid;
            } else if(f(mid,weights)>days) {
                left=mid+1;
            } else {
                right=mid;
            }
        }
        return left;

    }
    public int f(int x,int[] weights) {//x为自变量，表示载重，f(x)表示要花费的天数,为因变量
        // f(x) 随着 x 的增加单调递减
        int days=0;
        int len=weights.length;
        int i=0;
        while(i<len) {
            int cap=x;
            while(i<len) {
                if(cap<weights[i]) {
                    break;
                }else {
                    cap-=weights[i];
                }

                i++;
            }
            days++;
        }
        return days;
    }
}